package demo2;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * 快速排序挖坑法 前后指针法  hoare法
 * 快速排序非递归---栈
 * 快速排序---经典问题  ----- 荷兰国旗问题
 * 两种情况 :
 * 1. <=放在右边   >放在左边
 * 2. < 放在左边 =放在中间  < 放在右边
 * 对链表进行快速排序  ---  单链表  和   双链表
 * User: 石方旭
 * Date: 2022-07-08
 * Time: 9:13
 */
public class TestQuickSort {


    //前后指针法
    public static int partition(int[] arr,int left,int right){
        int prev = left;
        int cur = left+1;
        int pivot = left;
        while(cur<=right){
            //cur负责找小
            if(arr[cur]<arr[pivot]&& ++prev!=cur){
                 int tmp = arr[cur];
                 arr[cur] = arr[prev];
                 arr[prev] = tmp;
            }
            ++cur;
        }
        int tmp = arr[pivot];
        arr[pivot] = arr[prev];
        arr[prev] = tmp;
        return prev;
    }


    public static void quickSort(int[] arr,int left,int right){
        if(left>=right) return ;
        int mid = partition(arr,left,right);
        quickSort(arr,left,mid-1);
        quickSort(arr,mid+1,right);
    }

    public static void main(String[] args) {
        int[] arr = {9,8,5,6,47,8,2,1,0,2,30,56};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }



}
